/*
 * Board.cpp
 *
 *  Created on: May 30, 2011
 *      Author: hongyang
 */

#include "Board.h"
#include "../smartgame/SgStack.h"
#include <iostream>

//log4cpp::Category* Board::boardLog = 0;
int Board::count = 0;

namespace {
static const bool DEBUG_BOARD = false;
}

Board::Board() :
	boardConst(SG_MAX_SIZE) {
	init();
	count++;
	if (DEBUG_BOARD)
		SgDebug() << count << '\n';
}

Board::~Board() {
	blockList[SG_BLACK].Clear();
	blockList[SG_WHITE].Clear();
}

void Board::copy(const Board& b) {
	if (DEBUG_BOARD)
		SgDebug() << "copy\n";
	state.copy(b.state);
	moveInfo = b.moveInfo;
	numMoves = b.numMoves;
	SgVectorOf<Block> vec;
	for (BlockList::Iterator bit(b.blockList[SG_BLACK]); bit; ++bit) {
		const Block& block = *bit;
		if (!block.isDeleted())
			vec.Include(&block);
	}
	for (SgVectorIteratorOf<Block> bit(vec); bit; ++bit) {
		Block& block = createNewBlock(SG_BLACK);
		//SgDebug() << "create block " << &block << "\n";
		Block* gen = *bit;
		block.copy(*gen);
		setBlock(block);
	}
	for (BlockList::Iterator bit(b.blockList[SG_WHITE]); bit; ++bit) {
		const Block& gen = *bit;
		if (!gen.isDeleted())
			vec.Include(&gen);
	}
	for (SgVectorIteratorOf<Block> bit(vec); bit; ++bit) {
		Block& block = createNewBlock(SG_WHITE);
		//SgDebug() << "create block " << &block << "\n";
		Block* gen = *bit;
		block.copy(*gen);
		setBlock(block);
	}
//	moveStack.copy(b.moveStack);
/*	const StackEntry& s = b.moveStack;
	for (int i = 0; i < s.killed.Length(); i++) {
		Block* b = s.killed[i];
		Block* g = anchor(b->getAnchor());
		SG_ASSERT(g != 0);
		moveStack.killed.Include(g);
	}
	for (int i = 0; i < s.merged.Length(); i++) {
		Block* b = s.merged[i];
		Block* g = anchor(b->getAnchor());
		SG_ASSERT(g != 0);
		moveStack.merged.Include(g);
	}
*/
	if (DEBUG_BOARD)
		SgDebug() << "-------------copy\n";
	//print();
	checkConsistency();
}

void Board::setBlock(Block& b) {
	for (PointList::Iterator pit(b.getPoints()); pit; ++pit) {
		//SgDebug() << "set " << SgWritePoint(*pit) << " at " << &b << "\n";
		state.blocks[*pit] = &b;
	}
}

void Board::init() {
	//	if(boardLog == 0)
	//		boardLog = getLogger("board");
	if (DEBUG_BOARD)
		SgDebug() << "init board\n";
	state.numPrisoners[SG_BLACK] = 0;
	state.numPrisoners[SG_WHITE] = 0;
	state.numStones[SG_BLACK] = 0;
	state.numStones[SG_WHITE] = 0;
	state.toPlay = SG_BLACK;
	state.all.Clear();
	state.empty.Clear();

	for (SgPoint p = 0; p < SG_MAXPOINT; ++p) {
		state.color[p] = SG_BORDER;
		state.blocks[p] = 0;
		state.neighbors[SG_BLACK][p] = 0;
		state.neighbors[SG_WHITE][p] = 0;
	}

	for (SgGrid x = 1; x <= SG_MAX_SIZE; ++x)
		for (SgGrid y = 1; y <= SG_MAX_SIZE; ++y) {
			SgPoint p = SgPointUtil::Pt(x, y);
			state.color[p] = SG_EMPTY;
			state.empty.Include(p);
		}
	numMoves = 0;
	blockList[SG_BLACK].Clear();
	blockList[SG_WHITE].Clear();
	moveStack.clear();
}

void Board::addStone(Move m) {
	SgPoint p = m.Point();
	SgBlackWhite c = m.Color();
	state.color[p] = c;
	state.empty.Exclude(p);
	state.all[c].Include(p);
	state.toPlay = SgOppBW(c);
	++state.numStones[c];
	++numMoves;
	SgArray<int, SG_MAXPOINT>& nuNeighbors = state.neighbors[c];
	++nuNeighbors[p - SG_NS];
	++nuNeighbors[p - SG_WE];
	++nuNeighbors[p + SG_WE];
	++nuNeighbors[p + SG_NS];
}

void Board::removeStone(SgPoint p) {
	SgBlackWhite c = getColor(p);
	SG_ASSERT_BW(c);
	state.color[p] = SG_EMPTY;
	state.empty.Include(p);
	state.all[c].Exclude(p);
	--state.numStones[c];
	--numMoves;
	SgArray<int, SG_MAXPOINT>& nuNeighbors = state.neighbors[c];
	--nuNeighbors[p - SG_NS];
	--nuNeighbors[p - SG_WE];
	--nuNeighbors[p + SG_WE];
	--nuNeighbors[p + SG_NS];
}

void Board::play(Move m) {
	SgPoint p = m.Point();
	SgBlackWhite c = m.Color();
	if (DEBUG_BOARD)
		SgDebug() << SgBW(c) << " play " << SgPointUtil::PointToString(p)
				+ '\n';
	checkConsistency();
	SG_ASSERT(c == state.toPlay);
	if (!(isPass(p) || (isValid(p) && isEmpty(p)))) {
		moveInfo.set(GO_MOVEFLAG_ILLEGAL);
		return;
	}
	//moveStack.Resize(moveStack.Length() + 1);
	moveStack.clear();
	StackEntry& entry = moveStack;
	entry.move = m;

	if (isPass(p)) {
		SgDebug() << "pass\n";
		state.toPlay = SgOppBW(m.Color());
		return;
	}

	std::string s1;
	s1 += SgBW(c);
	addStone(m);

	tryKill(m, entry);
	if (entry.killed.Length() > 0) {
		moveInfo.set(GO_MOVEFLAG_CAPTURING);
	}

	bool isLegal = true;
	if (DEBUG_BOARD)
		SgDebug() << "update\n";
	updateBlocksAfterAdd(m, entry);

	entry.suicide = 0;
	if (checkSuicide(p, entry) && !setup.allowSuicide)
		isLegal = false;
	SgPoint ban = state.koBan;
	if (isValid(p) && p == ban)
		isLegal = false;
	if (!isLegal) {
		SgDebug() << "illegal move " << SgWritePoint(p) << "\n";
		moveInfo.set(GO_MOVEFLAG_ILLEGAL);
	}
	state.koBan = SG_NULLPOINT;

	if (entry.killed.Length() == 1) {
		Block* b = entry.killed[0];
		if (b->numPoints() == 1)
			state.koBan = b->getAnchor();
	}

	checkConsistency();
}

void Board::undo() {
	const StackEntry& entry = moveStack;//.Last();
	restoreState(entry);
	updateBlocksAfterUndo(entry);
	//moveStack.PopBack();
	checkConsistency();
}

void Board::restoreState(const StackEntry& entry) {
	state.toPlay = SgOppBW(state.toPlay);
}

void Board::updateBlocksAfterAdd(Move m, StackEntry& entry) {
	SgPoint p = m.Point();
	SgBlackWhite c = m.Color();
	if (numNeigh(p, c) == 0) {
		if (DEBUG_BOARD)
			SgDebug() << "create single block\n";
		entry.addedTo = 0;
		entry.isSingleStone = true;
		Block& block = createNewBlock(c);
		block.init(m);
		if (isEmpty(p - SG_NS))
			block.appendLib(p - SG_NS);
		if (isEmpty(p - SG_WE))
			block.appendLib(p - SG_WE);
		if (isEmpty(p + SG_WE))
			block.appendLib(p + SG_WE);
		if (isEmpty(p + SG_NS))
			block.appendLib(p + SG_NS);
		state.blocks[p] = &block;
		//SgDebug() << "set " << p << " " << SgWritePoint(p) << " " << &block << " " << state.blocks[111] << "\n";
	} else {
		if (DEBUG_BOARD)
			SgDebug() << "get adj blocks\n";
		SgArrayList<Block*, 4> adjBlocks = getAdjBlocks(p, c);
		if (DEBUG_BOARD)
			SgDebug() << "get adj blocks done\n";
		for (int i = 0; i < adjBlocks.Length(); i++) {
			Block* b = adjBlocks[i];
			SgPoint p = b->getAnchor();
			if (DEBUG_BOARD)
				SgDebug() << " adj block" << SgPointUtil::PointToString(p)
						<< "\n";
		}
		if (adjBlocks.Length() == 1) {
			Block* block = adjBlocks[0];
			addStoneToBlock(p, block, entry);
			entry.addedTo = block;
		} else {
			entry.addedTo = 0;
			entry.merged = adjBlocks;
			mergeBlocks(m, adjBlocks);
		}
	}
}

Block& Board::createNewBlock(SgBlackWhite color) {
	blockList[color].Resize(blockList[color].Length() + 1);
	Block& block = blockList[color].Last();
	block.clear();
	//SgDebug()<<"__new block "<< &block <<"\n";
	return block;
	//blockList[color].Include(&block);
}

SgArrayList<Block*, 4> Board::getAdjBlocks(SgPoint p, SgBlackWhite c) const {
	SgArrayList<Block*, 4> result;
	if (numNeigh(p, c) > 0) {
		Block* block;
		if (isColor(p - SG_NS, c))
			result.PushBack(state.blocks[p - SG_NS]);
		if (isColor(p - SG_WE, c) && !result.Contains(
				(block = state.blocks[p - SG_WE])))
			result.PushBack(block);
		if (isColor(p + SG_WE, c) && !result.Contains(
				(block = state.blocks[p + SG_WE])))
			result.PushBack(block);
		if (isColor(p + SG_NS, c) && !result.Contains(
				(block = state.blocks[p + SG_NS])))
			result.PushBack(block);
	}
	return result;
}

void Board::addStoneToBlock(SgPoint p, Block* block, StackEntry& entry) {
	// Stone already placed
	block->appendStone(p);
	// done in try kill
	//block->removeLib(p);
	entry.newLibs.Clear();
	if (isEmpty(p - SG_NS) && !adjTo(p - SG_NS, block)) {
		block->appendLib(p - SG_NS);
		entry.newLibs.PushBack(p - SG_NS);
	}
	if (isEmpty(p - SG_WE) && !adjTo(p - SG_WE, block)) {
		block->appendLib(p - SG_WE);
		entry.newLibs.PushBack(p - SG_WE);
	}
	if (isEmpty(p + SG_WE) && !adjTo(p + SG_WE, block)) {
		block->appendLib(p + SG_WE);
		entry.newLibs.PushBack(p + SG_WE);
	}
	if (isEmpty(p + SG_NS) && !adjTo(p + SG_NS, block)) {
		block->appendLib(p + SG_NS);
		entry.newLibs.PushBack(p + SG_NS);
	}
	state.blocks[p] = block;
	//SgDebug() << "set " << p << " " << SgWritePoint(p) << " " << block << "\n";
}

void Board::mergeBlocks(Move m, SgArrayList<Block*, 4> blocks) {
	if (DEBUG_BOARD)
		SgDebug() << "merge\n";
	SG_ASSERT(numNeigh(m.Point(), m.Color()) > 1);
	Block& block = createNewBlock(m.Color());
	block.init(m);
	SgMarker marker;
	SgReserveMarker reserve(marker);
	SG_UNUSED(reserve);
	marker.Clear();

	for (SgArrayList<Block*, 4>::Iterator it(blocks); it; ++it) {
		Block* b = *it;
		for (StoneIterator sit(b->getPoints()); sit; ++sit) {
			block.appendStone(*sit);
			state.blocks[*sit] = &block;
		}
		for (LibertyIterator lib(b->getLibs()); lib; ++lib)
			if (marker.NewMark(*lib))
				block.appendLib(*lib);
		b->setDelete();
	}

	SgPoint p = m.Point();
	state.blocks[p] = &block;

	if (isEmpty(p - SG_NS) && marker.NewMark(p - SG_NS))
		block.appendLib(p - SG_NS);
	if (isEmpty(p - SG_WE) && marker.NewMark(p - SG_WE))
		block.appendLib(p - SG_WE);
	if (isEmpty(p + SG_WE) && marker.NewMark(p + SG_WE))
		block.appendLib(p + SG_WE);
	if (isEmpty(p + SG_NS) && marker.NewMark(p + SG_NS))
		block.appendLib(p + SG_NS);
}

void Board::updateBlocksAfterUndo(const StackEntry& entry) {
	SgPoint p = entry.move.Point();
	if (isPass(p))
		return;

	SgBlackWhite c = entry.move.Color();
	state.numStones[c]--;
	state.blocks[p] = 0;

	Block* addedTo = entry.addedTo;
	if (addedTo != 0) {
		addedTo->popStone();
		for (SgArrayList<SgPoint, 4>::Iterator it(entry.newLibs); it; ++it)
			addedTo->removeLib(*it);
	} else {
		for (SgArrayList<Block*, 4>::Iterator it(entry.merged); it; ++it) {
			Block* block = *it;
			for (StoneIterator stn(block->getPoints()); stn; ++stn)
				state.blocks[*stn] = block;
		}
		blockList[c].PopBack();
	}
	for (SgArrayList<Block*, 4>::Iterator it(entry.killed); it; ++it)
		restoreKill(*it, SgOppBW(entry.move.Color()));
}

void Board::tryKill(Move m, StackEntry& entry) {
	entry.killed.Clear();
	SgPoint p = m.Point();
	SgBlackWhite c = m.Color(), opp = SgOppBW(c);
	if (numNeigh(p, SG_BLACK) == 0 && numNeigh(p, SG_WHITE) == 0)
		return;
	SgArrayList<Block*, 4> blocks = getAdjBlocks(p);
	for (SgArrayList<Block*, 4>::Iterator it(blocks); it; ++it) {
		Block* b = *it;
		b->removeLib(p);
		if (b->color() == opp && b->numLib() == 0) {
			entry.killed.PushBack(b);
			b->setDelete();
			killBlock(b);
		}
	}
}

void Board::killBlock(const Block* block) {
	SgBlackWhite c = block->color();
	SgBlackWhite opp = SgOppBW(c);
	if (DEBUG_BOARD)
		SgDebug() << "kill\n";
	for (StoneIterator it(block->getPoints()); it; ++it) {
		SgPoint stn = *it;
		addLibToAdjBlocks(stn, opp);
		removeStone(stn);
		if (DEBUG_BOARD)
			SgDebug() << SgPointUtil::PointToString(stn) << " killed\n";
		state.blocks[stn] = 0;
	}
	int nuStones = block->getPoints().Length();
	state.numStones[c] -= nuStones;
	state.numPrisoners[c] += nuStones;
}

void Board::addLibToAdjBlocks(SgPoint p, SgBlackWhite c) {
	if (numNeigh(p, c) == 0)
		return;
	SgArrayList<Block*, 4> blocks = getAdjBlocks(p, c);
	for (SgArrayList<Block*, 4>::Iterator it(blocks); it; ++it) {
		Block* block = *it;
		if (block != 0)
			block->appendLib(p);
	}
}

void Board::restoreKill(Block* block, SgBlackWhite c) {
	SgBlackWhite opp = SgOppBW(c);
	for (StoneIterator it(block->getPoints()); it; ++it) {
		SgPoint stn = *it;
		addStone(Move(c, stn));
		state.blocks[stn] = block;
		removeLibFromAdjBlocks(stn, opp);
	}
	int nuStones = block->getPoints().Length();
	state.numStones[c] += nuStones;
	state.numPrisoners[c] -= nuStones;
	SG_ASSERT(state.numPrisoners[c] >= 0);
}

void Board::removeLibFromAdjBlocks(SgPoint p, SgBlackWhite c) {
	if (numNeigh(p, c) == 0)
		return;
	SgArrayList<Block*, 4> blocks = getAdjBlocks(p, c);
	for (SgArrayList<Block*, 4>::Iterator it(blocks); it; ++it)
		(*it)->removeLib(p);
}

void Board::checkConsistency() const {
	int numberBlack = 0;
	int numberWhite = 0;
	for (SgPoint p = 0; p < SG_MAXPOINT; ++p) {
		if (isColor(p, SG_BORDER))
			continue;
		int c = state.color[p];
		SG_ASSERT_EBW(c);
		int n = 0;
		for (SgNb4Iterator it(p); it; ++it)
			if (state.color[*it] == SG_EMPTY)
				++n;
		//		SG_ASSERT(n == NumEmptyNeighbors(p));
		int m = 0;
		for (SgNb4Iterator it(p); it; ++it)
			if (state.color[*it] == SG_BLACK)
				++m;
		SG_ASSERT(m == numNeigh(p, SG_BLACK));
		int k = 0;
		for (SgNb4Iterator it(p); it; ++it)
			if (state.color[*it] == SG_WHITE)
				++k;
		SG_ASSERT(k == numNeigh(p, SG_WHITE));
		if (checkCorner(p))
			SG_ASSERT(k+m+n == 2);
		else if (checkEdge(p))
			SG_ASSERT(k+m+n == 3);
		else
			SG_ASSERT(k+m+n == 4);
		if (c == SG_BLACK || c == SG_WHITE) {
			SG_ASSERT(state.all[c].Contains(p));
			checkConsistencyBlock(p);
		}

		if (c == SG_BLACK)
			++numberBlack;
		if (c == SG_WHITE)
			++numberWhite;
		if (c == SG_EMPTY) {
			if (state.blocks[p] != 0) {
				SgDebug() << SgWritePoint(p);
				state.blocks[p]->print();
			}
			SG_ASSERT(state.blocks[p] == 0);
		}
	}
	SG_ASSERT(state.all[SG_BLACK].Size() == numberBlack);
	SG_ASSERT(state.all[SG_WHITE].Size() == numberWhite);
}

void Board::checkConsistencyBlock(SgPoint point) const {
	SG_ASSERT(!isEmpty(point));
	SgBlackWhite color = getColor(point);
	PointList stones;
	LibertyList liberties;
	SgMarker mark;
	SgStack<SgPoint, SG_MAXPOINT> stack;
	stack.Push(point);
	//SgDebug() << "start push " << SgWritePoint(point) << "\n";
	while (!stack.IsEmpty()) {
		SgPoint p = stack.Pop();
		if (isBorder(p) || !mark.NewMark(p))
			continue;
		if (getColor(p) == color) {
			stones.PushBack(p);
			//SgDebug() << " push " << SgWritePoint(p) << "\n";
			stack.Push(p - SG_NS);
			stack.Push(p - SG_WE);
			stack.Push(p + SG_WE);
			stack.Push(p + SG_NS);
		} else if (getColor(p) == SG_EMPTY)
			liberties.PushBack(p);
	}
	const Block* block = state.blocks[point];
	SG_DEBUG_ONLY(block);
	if (!stones.Contains(block->getAnchor())) {
		SgDebug() << "point " << point << " " << SgWritePoint(point) << " "
				<< block << "\n";
		SgDebug() << "anc " << block << " " << SgWritePoint(block->getAnchor())
				<< "\n";
		block->print();
	}
	SG_ASSERT(stones.Contains(block->getAnchor()));
	SG_ASSERT(color == block->color());
	if (!stones.SameElements(block->getPoints())) {
		for (int i = 0; i < stones.Length(); i++)
			SgDebug() << SgWritePoint(stones[i]) << " ";
		SgDebug() << "\n";
		const PointList& list = block->getPoints();
		for (int i = 0; i < list.Length(); i++)
			SgDebug() << SgWritePoint(list[i]) << " ";
		SgDebug() << "\n";
	}
	SG_ASSERT(stones.SameElements(block->getPoints()));
	SG_ASSERT(liberties.SameElements(block->getLibs()));
	SG_ASSERT(stones.Length() == numStones(point));
}

bool Board::checkSuicide(SgPoint p, StackEntry& entry) {
	if (numLibs(p) == 0) {
		entry.suicide = state.blocks[p];
		entry.suicide->setDelete();
		killBlock(entry.suicide);
		moveInfo.set(GO_MOVEFLAG_SUICIDE);
		return true;
	} else
		return false;
}

bool Board::checkEdge(SgPoint p) const {
	int c = SgPointUtil::Col(p), r = SgPointUtil::Row(p);
	return c == 1 || c == 13 || r == 1 || r == 13;
}

bool Board::checkCorner(SgPoint p) const {
	int c = SgPointUtil::Col(p), r = SgPointUtil::Row(p);
	return (c == 1 && r == 1) || (c == 1 && r == 13) || (c == 13 && r == 1)
			|| (c == 13 && r == 13);
}

float Board::estimateEmptyPts() const {
	float dif = 0;
	for (SgSetIterator sit(state.empty); sit; ++sit) {
		SgPoint p = *sit;
		int b = num8Neigh(p, SG_BLACK), w = num8Neigh(p, SG_WHITE);
		if (b > w) {
			if (b >= w + 2 || w == 0)
				dif++;
		} else if (b < w) {
			if (b + 2 <= w || b == 0)
				dif--;
		}
	}
	return dif;
}
